package elka.gis.postman.helper.impl;

import java.util.ArrayList;
import java.util.List;

import elka.gis.postman.bean.Edge;
import elka.gis.postman.bean.Graph;
import elka.gis.postman.bean.Path;
import elka.gis.postman.bean.Vertex;
import elka.gis.postman.helper.EulerCycleSearcher;

/**
 * Klasa sluzaca do wyszukiwania cyklu eurela
 * @author Wojtek
 *
 */
public class EulerCycleSearcherImpl implements EulerCycleSearcher {

	/**
	 * Wyszukuje cykl eurela
	 */
	public Path findEulerCycle(Graph graph) {
		Graph g = graph.copy();
		List<Edge> edges= dfs(g.getVertices().get(0),null);		
		Path p = new Path();
		p.setEdges(edges);
		
		return p;
	}
	
	/**
	 * Przeszukiwanie grafu w glab
	 * @param v
	 * @param edge
	 * @return
	 */
	public List<Edge> dfs(Vertex v,Edge edge){
		List<Edge> result = new ArrayList<Edge>();
		while(!v.getEdges().isEmpty()){
			Edge e = v.getEdges().get(0);
			Vertex x = chooseTargetVertex(e, v);
			x.getEdges().remove(e);
			v.getEdges().remove(e);
			result.addAll(0,dfs(x,e));
		}
		if(edge!=null)
		result.add(0,edge);
		return result;
	}
	
	
	private Vertex chooseTargetVertex(Edge e,Vertex startVertex){
		if(e.getStartPoint().equals(startVertex)){
			return e.getEndPoint();
		}else{
			return e.getStartPoint();
		}
	}

}
